import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] meetings = {
                {1,2,5},
                {2,3,8},
                {1,5,10}
        };
        for(int e: s.findAllPeople(6, meetings, 1)) {
            System.out.print(e + " ");
        }
    }

    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        /**
         * 找出知晓秘密的所有专家*/
        // 1 预处理
        initialize(n);
        // -对知情人初始化
        aware[0] = aware[firstPerson] = true;
        // -对原数据按照时间排升序
        Arrays.sort(meetings, (a, b) -> a[2] - b[2]);
        // -变量创建：时间段（初始0）、节点暂存结构（最大情况）
        int curTime = 0;
        // --注意：此处大小不应当以n为极限，而是要以总体元素为极限，因为一个元素会重复存入--
        int[] temporaryStorage = new int[20_0000];
        int TSIndex = 0;

        // 2 并查集处理
        // -按照会议时段为单位进行合并，并打上知情标签，一个单位结束后释放未知情的集合节点
        for(int[] e: meetings) {
            // -1 若进入新时段，则更新时段并释放未知情集合
            if(e[2] != curTime) {
                // -释放节点
                while(TSIndex > 0) {
                    int temporaryVariable = temporaryStorage[--TSIndex];
                    if(!aware[find(temporaryVariable)]) {
                        father[temporaryVariable] = temporaryVariable;
                    }
                }
                // -更新时段
                curTime = e[2];
            }
            // -2 若是为旧时段，则照常按照会议合并
            union(e[0], e[1]);
            temporaryStorage[TSIndex++] = e[0];
            temporaryStorage[TSIndex++] = e[1];
        }

        // 3 统计知情人数并返回
        List<Integer> answer = new LinkedList<>();
        for(int i = 0; i < n; i++) {
            // -- 注意，此处是要判断其代表元素，而不是本身！--
            if(aware[find(i)]) {
                answer.add(i);
            }
        }
        return answer;
    }

    // 建立朴素的并查集
    public static int MAX_N;
    public static int[] father;
    public static int[] stack;
    public static int[] size;
    public static boolean[] aware;

    public static void initialize(int n) {
        /**
         * 对并查集初始化*/
        MAX_N = n;
        father = new int[MAX_N];
        stack = new int[MAX_N];
        size = new int[MAX_N];
        aware = new boolean[MAX_N];
        for(int i = 0; i < MAX_N; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public static int find(int a) {
        /**
         * 查找a元素所在集合的代表元素，并作扁平化优化*/
        int i = 0;
        while(a != father[a]) {
            stack[i++] = a;
            a = father[a];
        }
        while(i > 0) {
            father[stack[--i]] = a;
        }
        return a;
    }

    public static boolean isSameSet(int a, int b) {
        /**
         * 判断a、b元素是否处于同一个集合中*/
        return find(a) == find(b);
    }

    public static void union(int a, int b) {
        /**
         * 合并a、b元素所在集合*/
        int fa = find(a);
        int fb = find(b);
        if(fa != fb) {
            if(size[fa] >= size[fb]) {
                size[fa] += size[fb];
                // -维护标签
                aware[fa] = aware[fa] || aware[fb];
                father[fb] = fa;
            } else {
                size[fb] += size[fa];
                aware[fb] = aware[fa] || aware[fb];
                father[fa] = fb;
            }
        }
    }
}































